package lecode01;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。
 *
 * 示例 1：
 *
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 * 示例 2：
 *
 * 输入：nums = [1]
 * 输出：1
 */
public class 最大子数组和53 {

    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
//        int[] nums = {-2,4,-2,4,-1,-1,-1};
//        int[] nums = {-1,-2,-3,0};
//        System.out.println("最大值: " + maxSubArray(nums));
        int i = maxSubArrayDivideWithBorder(nums, 0, nums.length - 1);
//        int i = maxSubArray3(nums);
//        int i = maxSubArray5(nums);
        System.out.println("最大值: " + i);
    }


    /**
     * 方法一： 暴力破解法,会超出时间
     * 两个指针循环相加
     */
    public static int maxSubArray(int[] nums) {
        int res = nums[0];
        for (int i = 0; i < nums.length; i++) {
            res = Math.max(nums[i], res);
            int sum = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                sum = sum + nums[j];
                res = Math.max(res, sum);
            }
        }
        return res;
    }


    /**
     * 方法二： 分治法
     *[-2,1,-3,4,-1,          2,1,-5,4]
     * -2,1,-3,  4,-1         2,1,    -5,4
     * -2,1, -3,  4, -1       2, 1,    -5, 4
     * -2, 1, -3,  4, -1      2, 1,    -5, 4
     *首先二分法分成最小的单个数字
     * 在左递归和右递归返回后，判断合并
     * 左边的最大值是：  从center向左累加到最左边start下标，期间记录下最大值
     * 右边的最大值是：  从center+1开始向右边累加到end下标，期间记录下最大值
     * 然后计算中间值
     * 最后比较三个，左右期间记录下最大值、中间值的大小返回
     * 其中重点是center改变就会重新计算左右新的最大最小值，拆分的时候center递减，合并的时候center在递增
     *
     * -1,-2,-3,0
     */
    private static int maxSubArrayDivideWithBorder(int[] nums, int start, int end) {
        if (start == end) {
            return nums[start];
        }
        //计算中间下标
        int center = (start + end) / 2;
        //计算左边最大值
        int leftMax = maxSubArrayDivideWithBorder(nums, start, center);
        //计算右边最大值 从center+1开始
        int rightMax = maxSubArrayDivideWithBorder(nums, center+1, end);

        //计算左边center到start累计期间的最大值
        int leftCenterMax = Integer.MIN_VALUE;
        int leftCenterSum = 0;
        for (int i = center; i >= start; i--) {
            leftCenterSum += nums[i];
            leftCenterMax = Math.max(leftCenterSum, leftCenterMax);
        }

        //计算右边center+1到end累计期间的最大值
        int rightCenterMax = nums[center+1];
        int rightCenterSum = 0;
        for (int i = center+1; i <= end; i++) {
            rightCenterSum += nums[i];
            rightCenterMax = Math.max(rightCenterSum, rightCenterMax);
        }

        //计算中间值
        int centerMax = leftCenterMax + rightCenterMax;
        //返回最大值
//        return Math.max(Math.max(leftCenterMax, rightCenterMax), centerMax);
        return Math.max(centerMax, Math.max(leftMax, rightMax));

    }



    /**
     *方法三： 动态规划，就是当前值与前面值累加的最大值作比较，其实就是将暴力破解的双重for循环优化为单层for循环
     * [-2,1,-3,4,-1,2,1,-5,4]
     *
     */
    public static   int maxSubArray3(int[] nums) {
        //第一步：定义一个长度为nums长度的数组，用来记录期间产生的个部分的最大值
        int[] dp = new int[nums.length];
        //第二步：计算下标i到nums.length-1期间的连续数组的最大值
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);
        }
        //第三步：返回数组中的最大值
        return Arrays.stream(dp).max().getAsInt();
    }

    /**
     * 方法四：
     * @param nums  [-2,1,-3,4,-1,2,1,-5,4]
     * @return int
     */
    public static int maxSubArray4(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int minPreSum = 0;
        int preSum = 0;
        for(int num : nums){
            preSum += num;
            ans = Math.max(ans,preSum-minPreSum);
            minPreSum = Math.min(minPreSum,preSum);
        }
        return ans;
    }

    /**
     * 方法五：
     * @param nums [-2,1,-3,4,-1,2,1,-5,4]  [-2,4,-2,4,-1,-1,-1]
     * @return res
     * 第一步：看sum是否大于0 sum大于0才需要把当前sum部分往后加，如果小于等于0当前sum就不需要了（丢弃）
     * 第二步：判断ans与sum的大小
     */
    public static  int maxSubArray5(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for(int num: nums) {
            //sum大于0往后加
            if(sum > 0) {
                sum += num;
            } else {
                //sum小于等于0 直接丢弃
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }


}
